// 快速排序 取一个值，把大的放右边，小的放左边，递归进行，直到排序完成
// 记录一个索引l从数组最左侧开始，记录一个索引r从数组右侧开始
// 在l<r的条件下，找到右侧小于target的值array[r]，并将其赋值到array[l]
// 在l<r的条件下，找到左侧大于target的值array[l]，并将其赋值到array[r]
// 这样让l=r时，左侧的值全部小于target，右侧的值全部小于target，将target放到该位置

function quickSort (arr, start, end) {
  if (end - start < 1) return
  let l = start
  let r = end
  // 将第一个元素提取出来,并留出空间,以便后面的调换元素
  // [6,5,4,3,2,1,9,8,7]
  // target = 6 [,5,4,3,2,1,9,8,7]
  // 然后把小的移到左边,就可以把右边原本小的的空间又留出来,依次类推
  let target = arr[l]
  while (l < r) {
    while (l < r && target < arr[r]) {
      r --
    }
    arr[l] = arr[r]
    while (l < r && target > arr[l]) {
      l++
    }
    arr[r] = arr[l]
  }
  // 最后把目标元素放到中间
  arr[l] = target
  quickSort(arr, start, l - 1)
  quickSort(arr, l + 1, end)
}

let arr = [9,8,6,7,5,2,4,3,1]
quickSort(arr, 0, arr.length - 1)
console.log(arr)